{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Profit From Trading Stocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大股票收益"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的数组 <code>present</code> 和 <code>future</code> ，<code>present[i]</code> 和 <code>future[i]</code> 分别代表第 <code>i</code> 支股票现在和将来的价格。每支股票你最多购买 <strong>一次</strong> ，你的预算为 <code>budget</code> 。</p>\n",
    "\n",
    "<p>求最大的收益。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>present = [5,4,6,2,3], future = [8,5,4,3,5], budget = 10\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>你可以选择购买第 0,3,4 支股票获得最大收益：6 。总开销为：5 + 2 + 3 = 10 , 总收益是: 8 + 3 + 5 - 10 = 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>present = [2,2,5], future = [3,4,10], budget = 6\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>你可以选择购买第 2 支股票获得最大收益：5 。总开销为：5 , 总收益是: 10 - 5 = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>present = [3,3,12], future = [0,3,15], budget = 10\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>你无法购买唯一一支正收益股票 2 ，因此你的收益是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == present.length == future.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= present[i], future[i] &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= budget &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-profit-from-trading-stocks](https://leetcode.cn/problems/maximum-profit-from-trading-stocks/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-profit-from-trading-stocks](https://leetcode.cn/problems/maximum-profit-from-trading-stocks/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,4,6,2,3]\\n[8,5,4,3,5]\\n10', '[2,2,5]\\n[3,4,10]\\n6', '[3,3,12]\\n[0,3,15]\\n10']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        dp = [0] * (budget+1)\n",
    "        for i in range(n):\n",
    "            if future[i] > present[i]:\n",
    "                for j in range(budget, -1, -1):\n",
    "                    if j < present[i]:\n",
    "                        break\n",
    "                    if (s := dp[j-present[i]] + future[i] - present[i]) > dp[j]:\n",
    "                        dp[j] = s\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "       n = len(present)\n",
    "       dp = [0]*(budget+1)\n",
    "       for i in range(n):\n",
    "           j = budget\n",
    "           while j-present[i] >= 0:\n",
    "               dp[j] = max(dp[j], dp[j-present[i]]+future[i]-present[i])\n",
    "               j -= 1\n",
    "       res = 0\n",
    "       return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        lst = []\n",
    "        for p, f in zip(present, future):\n",
    "            delta = f - p \n",
    "            if delta > 0 and p <= budget:\n",
    "                lst.append([delta, p])\n",
    "        dp = [0] * (budget + 1)\n",
    "        for delta, p in lst:\n",
    "            for i in range(budget, p - 1, -1):\n",
    "                dp[i] = max(dp[i], dp[i - p] + delta)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        #背包问题\n",
    "        value=[f-p for f,p in zip(future,present)]\n",
    "        bag=[0]*(budget+1)\n",
    "        n=len(present)\n",
    "        for i in range(n):\n",
    "            cost=present[i]\n",
    "            for j in range(budget,cost-1,-1):\n",
    "                bag[j]=max(bag[j],bag[j-cost]+value[i])\n",
    "        return bag[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        dp=[0]*(budget+1)\n",
    "        cnt=collections.Counter()\n",
    "        #for p,f in zip(present,future):\n",
    "          #  if (f-p)>0 and p<=budget:\n",
    "            #    dp[p]=max(dp[p],f-p)\n",
    "             #   cnt[p]=max(cnt[p],f-p)\n",
    "\n",
    "\n",
    "        for p,f in zip(present,future):\n",
    "            for i in range(budget,-1,-1):\n",
    "                if f-p>0 and i>=p :\n",
    "                    #print(i+p)\n",
    "                    dp[i]=max(dp[i],dp[i-p]+f-p)\n",
    "                   # print(dp[i+p])\n",
    "        #print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        # 0 1 背包问题 i表示物品下标，j表示空间 \n",
    "        n = len(present)\n",
    "        dp = [0]*(budget+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            # print(dp)\n",
    "            for j in range(budget, present[i]-1, -1):\n",
    "                    # 不放入当前物品 或者 在够当前物品的空间下放入\n",
    "                dp[j] = max(dp[j], dp[j-present[i]]+future[i]-present[i])\n",
    "              \n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        dp = [0] * (budget+1)\n",
    "        for i in range(n):\n",
    "            if future[i] > present[i]:\n",
    "                for j in range(budget, present[i]-1, -1):\n",
    "                    if (s := dp[j-present[i]] + future[i] - present[i]) > dp[j]:\n",
    "                        dp[j] = s\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        # 存储可能赚钱的股票的收益和当前价格\n",
    "        lst = []\n",
    "        for p, f in zip(present, future):\n",
    "            delta = f - p\n",
    "            if delta > 0 and p <= budget:\n",
    "                lst.append([delta, p])\n",
    "\n",
    "        # 初始化DP数组\n",
    "        dp = [0] * (budget + 1)\n",
    "        \n",
    "        # 更新DP数组\n",
    "        for delta, p in lst:\n",
    "            for i in range(budget, p - 1, -1):\n",
    "                dp[i] = max(dp[i], dp[i - p] + delta)\n",
    "                \n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        dp = [0] * (budget+1)\n",
    "        for i in range(n):\n",
    "            for j in range(budget, -1, -1):\n",
    "                if j >= present[i]:\n",
    "                    dp[j] = max(dp[j], dp[j-present[i]] + future[i] - present[i])\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        has = [0] * (budget+1)\n",
    "        for i,j in zip(present,future):\n",
    "            if j > i:\n",
    "                for k in range(budget, i-1, -1):\n",
    "                    has[k] = max(has[k],has[k-i]+j-i)\n",
    "        return has[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dp\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        has = [0] * (budget+1)\n",
    "        for i,j in zip(present, future):\n",
    "            if j > i:\n",
    "                for k in range(budget, i-1, -1):\n",
    "                    has[k] = max(has[k], has[k-i] + j - i)\n",
    "\n",
    "        return has[-1]\n",
    "\n",
    "\n",
    "\n",
    "    # dfs\n",
    "    def maximumProfit2(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        @cache\n",
    "        def dp(i, left):\n",
    "            if i == len(present):\n",
    "                return 0\n",
    "\n",
    "            if left - present[i] < 0:\n",
    "                return dp(i + 1, left)\n",
    "\n",
    "            return max(dp(i + 1, left), dp(i + 1, left - present[i]) + future[i] - present[i])\n",
    "\n",
    "        res = dp(0, budget)\n",
    "        dp.cache_clear()\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        #背包问题\n",
    "        bag=[0]*(budget+1)\n",
    "        n=len(present)\n",
    "        for i in range(n):\n",
    "            cost=present[i]\n",
    "            for j in range(budget,cost-1,-1):\n",
    "                bag[j]=max(bag[j],bag[j-cost]+future[i]-cost)\n",
    "        return bag[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        f = [0] * (budget + 1)\n",
    "        for p, fu in zip(present, future):\n",
    "            for i in range(budget, p - 1, -1):\n",
    "                f[i] = max(f[i], f[i - p] + fu - p)\n",
    "        return f[budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        dp = [0] * (budget+1)\n",
    "        for i in range(n):\n",
    "            for j in range(budget, -1, -1):\n",
    "                if j >= present[i] and future[i] > present[i]:\n",
    "                    dp[j] = max(dp[j], dp[j-present[i]] + future[i] - present[i])\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        dp = [0] * (budget+1)\n",
    "        for i in range(n):\n",
    "            for j in range(budget, -1, -1):\n",
    "                if j >= present[i] and future[i] > present[i] and (s := dp[j-present[i]] + future[i] - present[i]) > dp[j]:\n",
    "                    dp[j] = s\n",
    "\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        dp=[0]+[-inf]*(budget)\n",
    "        for p,f in zip(present,future):\n",
    "            if f-p>0:\n",
    "                for i in range(budget-p+1):\n",
    "                    dp[budget-i]=max(dp[budget-i],dp[budget-i-p]+f-p)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        dp=[-inf]*(budget+1)\n",
    "        dp[0]=0\n",
    "        for p,f in zip(present,future):\n",
    "            for i in range(budget-p+1):\n",
    "                dp[budget-i]=max(dp[budget-i],dp[budget-i-p]+f-p)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        profit = []\n",
    "        for i in range(n):\n",
    "            if budget >= present[i]:\n",
    "                _ = future[i] - present[i]\n",
    "                profit.append([present[i], _])\n",
    "        dp = [0] * (budget+1)\n",
    "        for i, j in profit:\n",
    "            for k in range(budget, i-1, -1):\n",
    "                dp[k] = max(dp[k], dp[k-i]+j)\n",
    "        \n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        profit = [future[i]-present[i] for i in range(len(present))]\n",
    "        profit_id = [i for i in range(len(profit)) if profit[i] > 0]\n",
    "        profit = [profit[i] for i in profit_id]\n",
    "        present = [present[i] for i in profit_id]\n",
    "        future = [future[i] for i in profit_id]\n",
    "        if len(profit) == 0:\n",
    "            return 0\n",
    "        dp = [[0 for _ in range(budget+1)] for _ in range(len(profit))]\n",
    "        for j in range(budget+1):\n",
    "            dp[0][j] = 0 if j < present[0] else profit[0]\n",
    "        for i in range(len(profit)):\n",
    "            dp[i][0] = 0 if present[i] > 0 else profit[i]\n",
    "        for i in range(1, len(profit)):\n",
    "            dp[i][0] = dp[i][0] + dp[i-1][0]\n",
    "        \n",
    "        for i in range(1, len(profit)):\n",
    "            for j in range(1, budget+1):\n",
    "                if j-present[i] >= 0:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-present[i]]+profit[i])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n=len(present)\n",
    "        dp=[ [0]*(budget+1)for _ in range(n+1)] \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(budget+1):\n",
    "                if j<present[i-1]:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-present[i-1]]+future[i-1]-present[i-1])\n",
    "        return dp[n][budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        arr = [(x, y) for x,y in zip(present, future) if y > x]\n",
    "        n = len(arr) \n",
    "        dp = [[0] * (budget+1) for _ in range(n+1)]\n",
    "        #print(arr) \n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(budget+1):\n",
    "                dp[i][j] = dp[i-1][j] \n",
    "                if j >= arr[i-1][0]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i-1][j-arr[i-1][0]] + arr[i-1][1] - arr[i-1][0]) \n",
    "        return dp[n][budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        m = len(present)\n",
    "        profit_matrix = [[0] * (budget + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            for j in range(budget + 1):\n",
    "                if i == 0:\n",
    "                    profit_matrix[i][j] = 0\n",
    "                else:\n",
    "                    if present[i - 1] > j:\n",
    "                        profit_matrix[i][j] = profit_matrix[i - 1][j]\n",
    "                    else:\n",
    "                        profit_matrix[i][j] = max(profit_matrix[i - 1][j], profit_matrix[i - 1][j - present[i - 1]] + future[i - 1] - present[i - 1])\n",
    "        \n",
    "        return profit_matrix[m][budget]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        ans = 0\n",
    "        n = len(present)\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if j < 0:\n",
    "        #         return -inf\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     return max(dfs(i - 1, j), dfs(i - 1, j - present[i]) + future[i] - present[i])\n",
    "        # return dfs(n - 1, budget)\n",
    "\n",
    "        #dp[i][j] = dp[i - 1][j - present[i]] + future[i] - present[i]\n",
    "        dp = [[0] * (budget + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(budget + 1):\n",
    "                dp[i+1][j] = dp[i][j]\n",
    "                if j - present[i] >= 0:\n",
    "                    dp[i+1][j] = max(dp[i+1][j], dp[i][j - present[i]] + future[i] - present[i])\n",
    "        return dp[n][budget]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        f = [[0] * (budget+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(0, budget+1):\n",
    "                f[i][j] = f[i-1][j]\n",
    "                if j - present[i-1] >= 0:\n",
    "                    f[i][j] = max(f[i][j], f[i-1][j-present[i-1]] + future[i-1] - present[i-1])\n",
    "        return f[-1][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "        dp = [[0] * (budget + 1) for _ in range(n + 1)]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(budget + 1):\n",
    "                if j < present[i - 1]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - present[i - 1]] + future[i - 1] - present[i - 1])\n",
    "        \n",
    "        return dp[n][budget]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        N = len(present)\n",
    "        # 每行代表一件商品，每列代表budjet余额\n",
    "        dp = [[0]*(budget+2) for _ in range(N+1)]\n",
    "        \n",
    "        for i in range(1, N+1):\n",
    "            for j in range(budget+1):\n",
    "                # 余额不足以购买当前产品\n",
    "                if j<present[i-1]: dp[i][j] = dp[i-1][j]\n",
    "                # 购买当前产品利润大还是不购买利润大\n",
    "                else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-present[i-1]]+future[i-1]-present[i-1])\n",
    "\n",
    "        return dp[N][budget]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        dp = [[0]*(budget+1) for i in range(len(present)+1)]\n",
    "        for i in range(1, len(present)+1):\n",
    "            for j in range(budget+1):\n",
    "                if j >= present[i-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j - present[i-1]] + future[i-1] -present[i-1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[len(present)][budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        # 0 1 背包问题 i表示物品下标，j表示空间 \n",
    "        n = len(present)\n",
    "        dp = [[0]*(budget+1) for i in range(n+1)]\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(budget+1):\n",
    "                # if j == 0:\n",
    "                #     dp[i][j] = 0 \n",
    "                #     continue\n",
    "                if j >= present[i-1]:  \n",
    "                    # 不放入当前物品 或者 在够当前物品的空间下放入\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-present[i-1]]+future[i-1]-present[i-1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[n][budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        # dp[i][j] 表示在前i股票中选择购买且总开销不超过j的情况下的最大收益。\n",
    "        n = len(present)\n",
    "        dp = [[0]*(budget+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(budget+1):\n",
    "                if j < present[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-present[i-1]]+future[i-1]-present[i-1])\n",
    "        return dp[n][budget]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        line=[]\n",
    "        for idt in range(len(present)):\n",
    "            line.append(future[idt]-present[idt])\n",
    "\n",
    "        dp=[[0]*(budget+1) for i in range(len(present))]\n",
    "\n",
    "        for j in range(budget+1):\n",
    "            if j>=present[0]:\n",
    "                dp[0][j]=max(0,line[0])\n",
    "        for i in range(1,len(present)):\n",
    "            for j in range(budget+1):\n",
    "\n",
    "                if j>=present[i]:\n",
    "                    dp[i][j]=max(dp[i-1][j-present[i]]+max(0,line[i]),dp[i-1][j])\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        items = []\n",
    "        n = len(present)\n",
    "        for i in range(n):\n",
    "            reward = future[i]-present[i]\n",
    "            if reward>0:\n",
    "                items.append([present[i], reward])\n",
    "        # 背包问题\n",
    "        n = len(items)\n",
    "        # print(items)\n",
    "        if n==0:\n",
    "            return 0\n",
    "        f = [[0 for _ in range(budget+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(budget+1):\n",
    "                if j>=items[i-1][0]:\n",
    "                    left = j-items[i-1][0]\n",
    "                    f[i][j] = max(f[i-1][j], f[i-1][left]+ items[i-1][1])\n",
    "                else:\n",
    "                    f[i][j] = f[i-1][j]\n",
    "        return f[-1][budget]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        ls=[]\n",
    "        n=len(present)\n",
    "        for i in range(n):\n",
    "            p=present[i]\n",
    "            f=future[i]\n",
    "            if p<f:\n",
    "                ls.append([p,f-p])\n",
    "        m=len(ls)\n",
    "        dp=[[0 for _ in range(budget+1)]for _ in range(m+1)]\n",
    "        #print(dp)\n",
    "        for i in range(1,m+1):\n",
    "            cost,win=ls[i-1]\n",
    "            #print(cost,win)\n",
    "            for j in range(min(cost,budget+1)):\n",
    "                dp[i][j]=dp[i-1][j]\n",
    "            for j in range(cost,budget+1):\n",
    "                #print(j,dp[i-1][j],dp[i-1][j-cost],win)\n",
    "                dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost]+win)\n",
    "        #print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        dp = [[-1] * 1001 for _ in range(len(present))]\n",
    "        def dfs(idx, count):\n",
    "            if idx == len(present):\n",
    "                return 0\n",
    "            if dp[idx][count] != -1:\n",
    "                return dp[idx][count]\n",
    "            res = dfs(idx + 1, count)\n",
    "            if count >= present[idx]:\n",
    "                res = max(res, dfs(idx + 1, count - present[idx]) + future[idx] - present[idx])\n",
    "            dp[idx][count] = res\n",
    "            return res\n",
    "        return dfs(0, budget)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumProfit(self, present: List[int], future: List[int], budget: int) -> int:\n",
    "        n = len(present)\n",
    "\n",
    "        @cache\n",
    "        def f(rest, i):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            earning = future[i] - present[i]\n",
    "            res = f(rest, i + 1)\n",
    "            if earning <= 0 or rest < present[i]:\n",
    "                return res \n",
    "            # if rest >= present[i]:\n",
    "            return max(res, f(rest - present[i], i + 1) + earning)\n",
    "            \n",
    "\n",
    "        ans = f(budget, 0)\n",
    "        f.cache_clear()\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
